home *** CD-ROM | disk | FTP | other *** search
/ World of Education / World of Education.iso / world_s / sp12src.zip / BLOOM.ASM next >
Assembly Source File  |  1991-03-27  |  12KB  |  344 lines
  1. IDEAL
  2. ; This program implements the hashing and bit setting mechanics for
  3. ; superimposed coding (Bloom Filter) using CRC.
  4. ;
  5. ; CRC-32 routine and tables were converted from code discovered
  6. ; in the DEZIP.PAS V2.0 by R. P. Byrne.  From comments there:
  7. ;
  8. ;   Converted to Turbo Pascal (tm) V4.0 March, 1988 by J.R.Louvau
  9. ;   COPYRIGHT (C) 1986 Gary S. Brown: "You may use this program, or
  10. ;   code or tables extracted from it, as desired without restriction."
  11. ;
  12. ; This is the 32-bit CRC used by PKZIP and Forsberg's DSZ.
  13. ;
  14. ; The remainder of this code is Copyright 1990 by Edwin T. Floyd.
  15. ;
  16. ;   Edwin T. Floyd [76067,747]
  17. ;   #9 Adams Park Ct.
  18. ;   Columbus, GA 31909
  19. ;   404-576-3305 (work)
  20. ;   404-322-0076 (home)
  21. ;
  22. ; Borland's Turbo Assembler - TASM is required to assemble this program.
  23. ;
  24. SEGMENT  code BYTE PUBLIC
  25.          ASSUME cs:code
  26.  
  27. ;            0
  28. crc32tab dd     000000000h, 077073096h, 0ee0e612ch, 0990951bah
  29.          dd     0076dc419h, 0706af48fh, 0e963a535h, 09e6495a3h
  30.          dd     00edb8832h, 079dcb8a4h, 0e0d5e91eh, 097d2d988h
  31.          dd     009b64c2bh, 07eb17cbdh, 0e7b82d07h, 090bf1d91h
  32. ;            1
  33.          dd     01db71064h, 06ab020f2h, 0f3b97148h, 084be41deh
  34.          dd     01adad47dh, 06ddde4ebh, 0f4d4b551h, 083d385c7h
  35.          dd     0136c9856h, 0646ba8c0h, 0fd62f97ah, 08a65c9ech
  36.          dd     014015c4fh, 063066cd9h, 0fa0f3d63h, 08d080df5h
  37. ;            2
  38.          dd     03b6e20c8h, 04c69105eh, 0d56041e4h, 0a2677172h
  39.          dd     03c03e4d1h, 04b04d447h, 0d20d85fdh, 0a50ab56bh
  40.          dd     035b5a8fah, 042b2986ch, 0dbbbc9d6h, 0acbcf940h
  41.          dd     032d86ce3h, 045df5c75h, 0dcd60dcfh, 0abd13d59h
  42. ;            3
  43.          dd     026d930ach, 051de003ah, 0c8d75180h, 0bfd06116h
  44.          dd     021b4f4b5h, 056b3c423h, 0cfba9599h, 0b8bda50fh
  45.          dd     02802b89eh, 05f058808h, 0c60cd9b2h, 0b10be924h
  46.          dd     02f6f7c87h, 058684c11h, 0c1611dabh, 0b6662d3dh
  47. ;            4
  48.          dd     076dc4190h, 001db7106h, 098d220bch, 0efd5102ah
  49.          dd     071b18589h, 006b6b51fh, 09fbfe4a5h, 0e8b8d433h
  50.          dd     07807c9a2h, 00f00f934h, 09609a88eh, 0e10e9818h
  51.          dd     07f6a0dbbh, 0086d3d2dh, 091646c97h, 0e6635c01h
  52. ;            5
  53.          dd     06b6b51f4h, 01c6c6162h, 0856530d8h, 0f262004eh
  54.          dd     06c0695edh, 01b01a57bh, 08208f4c1h, 0f50fc457h
  55.          dd     065b0d9c6h, 012b7e950h, 08bbeb8eah, 0fcb9887ch
  56.          dd     062dd1ddfh, 015da2d49h, 08cd37cf3h, 0fbd44c65h
  57. ;            6
  58.          dd     04db26158h, 03ab551ceh, 0a3bc0074h, 0d4bb30e2h
  59.          dd     04adfa541h, 03dd895d7h, 0a4d1c46dh, 0d3d6f4fbh
  60.          dd     04369e96ah, 0346ed9fch, 0ad678846h, 0da60b8d0h
  61.          dd     044042d73h, 033031de5h, 0aa0a4c5fh, 0dd0d7cc9h
  62. ;            7
  63.          dd     05005713ch, 0270241aah, 0be0b1010h, 0c90c2086h
  64.          dd     05768b525h, 0206f85b3h, 0b966d409h, 0ce61e49fh
  65.          dd     05edef90eh, 029d9c998h, 0b0d09822h, 0c7d7a8b4h
  66.          dd     059b33d17h, 02eb40d81h, 0b7bd5c3bh, 0c0ba6cadh
  67. ;            8
  68.          dd     0edb88320h, 09abfb3b6h, 003b6e20ch, 074b1d29ah
  69.          dd     0ead54739h, 09dd277afh, 004db2615h, 073dc1683h
  70.          dd     0e3630b12h, 094643b84h, 00d6d6a3eh, 07a6a5aa8h
  71.          dd     0e40ecf0bh, 09309ff9dh, 00a00ae27h, 07d079eb1h
  72. ;            9
  73.          dd     0f00f9344h, 08708a3d2h, 01e01f268h, 06906c2feh
  74.          dd     0f762575dh, 0806567cbh, 0196c3671h, 06e6b06e7h
  75.          dd     0fed41b76h, 089d32be0h, 010da7a5ah, 067dd4acch
  76.          dd     0f9b9df6fh, 08ebeeff9h, 017b7be43h, 060b08ed5h
  77. ;            A
  78.          dd     0d6d6a3e8h, 0a1d1937eh, 038d8c2c4h, 04fdff252h
  79.          dd     0d1bb67f1h, 0a6bc5767h, 03fb506ddh, 048b2364bh
  80.          dd     0d80d2bdah, 0af0a1b4ch, 036034af6h, 041047a60h
  81.          dd     0df60efc3h, 0a867df55h, 0316e8eefh, 04669be79h
  82. ;            B
  83.          dd     0cb61b38ch, 0bc66831ah, 0256fd2a0h, 05268e236h
  84.          dd     0cc0c7795h, 0bb0b4703h, 0220216b9h, 05505262fh
  85.          dd     0c5ba3bbeh, 0b2bd0b28h, 02bb45a92h, 05cb36a04h
  86.          dd     0c2d7ffa7h, 0b5d0cf31h, 02cd99e8bh, 05bdeae1dh
  87. ;            C
  88.          dd     09b64c2b0h, 0ec63f226h, 0756aa39ch, 0026d930ah
  89.          dd     09c0906a9h, 0eb0e363fh, 072076785h, 005005713h
  90.          dd     095bf4a82h, 0e2b87a14h, 07bb12baeh, 00cb61b38h
  91.          dd     092d28e9bh, 0e5d5be0dh, 07cdcefb7h, 00bdbdf21h
  92. ;            D
  93.          dd     086d3d2d4h, 0f1d4e242h, 068ddb3f8h, 01fda836eh
  94.          dd     081be16cdh, 0f6b9265bh, 06fb077e1h, 018b74777h
  95.          dd     088085ae6h, 0ff0f6a70h, 066063bcah, 011010b5ch
  96.          dd     08f659effh, 0f862ae69h, 0616bffd3h, 0166ccf45h
  97. ;            E
  98.          dd     0a00ae278h, 0d70dd2eeh, 04e048354h, 03903b3c2h
  99.          dd     0a7672661h, 0d06016f7h, 04969474dh, 03e6e77dbh
  100.          dd     0aed16a4ah, 0d9d65adch, 040df0b66h, 037d83bf0h
  101.          dd     0a9bcae53h, 0debb9ec5h, 047b2cf7fh, 030b5ffe9h
  102. ;            F
  103.          dd     0bdbdf21ch, 0cabac28ah, 053b39330h, 024b4a3a6h
  104.          dd     0bad03605h, 0cdd70693h, 054de5729h, 023d967bfh
  105.          dd     0b3667a2eh, 0c4614ab8h, 05d681b02h, 02a6f2b94h
  106.          dd     0b40bbe37h, 0c30c8ea1h, 05a05df1bh, 02d02ef8dh
  107.  
  108.  
  109.          MODEL TPASCAL
  110.  
  111. PROC     CRCBlock NEAR
  112. ; Compute 32 bit CRC for block of data pointed to by DS:SI.  Starting and
  113. ; ending CRC is in DX:AX, length of data block is in CX.  In addition to
  114. ; these registers this routine stomps ES and BX.
  115.          cld
  116. @@loop:
  117.          xor    bh,bh
  118.          mov    bl,al
  119.          lodsb
  120.          xor    bl,al
  121.          mov    al,ah
  122.          mov    ah,dl
  123.          mov    dl,dh
  124.          xor    dh,dh
  125.          shl    bx,1
  126.          shl    bx,1
  127.          les    bx,[crc32tab+bx]
  128.          xor    ax,bx
  129.          mov    bx,es
  130.          xor    dx,bx
  131.          loop   @@loop
  132.          ret
  133. ENDP
  134.  
  135. PROC     NextNullCRC NEAR
  136. ; Compute the next CRC in DX:AX as if the buffer were extended with a null
  137. ; byte.  This routine also stomps ES and BX.
  138.          xor    bh,bh
  139.          mov    bl,al
  140.          mov    al,ah
  141.          mov    ah,dl
  142.          mov    dl,dh
  143.          xor    dh,dh
  144.          shl    bx,1
  145.          shl    bx,1
  146.          les    bx,[crc32tab+bx]
  147.          xor    ax,bx
  148.          mov    bx,es
  149.          xor    dx,bx
  150.          ret
  151. ENDP
  152.  
  153. PROC     TestBit NEAR
  154. ; Test a bit, bit number in DX:AX, table pointed to by DS:SI, size of
  155. ; table in bytes in DI.  Stomps BX.  Value of bit in flags, Z/NZ.
  156.          push   cx
  157.          push   dx
  158.          push   ax
  159.          mov    cl,al         ; bl := bit mask
  160.          and    cl,07h
  161.          mov    bl,80h
  162.          shr    bl,cl
  163.          shr    dx,1          ; dx:ax := byte offset
  164.          rcr    ax,1
  165.          shr    dx,1
  166.          rcr    ax,1
  167.          shr    dx,1
  168.          rcr    ax,1
  169.          cmp    di,dx         ; dx := byte offset MOD table size
  170.          ja     @@quickdiv
  171.          mov    cx,di         ; (protect against overflow)
  172.          jcxz   @@notable
  173. @@protloop:
  174.          shl    cx,1
  175.          cmp    cx,dx
  176.          jbe    @@protloop
  177.          div    cx
  178.          mov    ax,dx
  179.          xor    dx,dx
  180. @@quickdiv:
  181.          div    di
  182.          mov    ax,si
  183.          add    si,dx         ; ds:si points to byte
  184.          and    bl,[si]       ; test it
  185.          mov    si,ax
  186. @@notable:
  187.          pop    ax
  188.          pop    dx
  189.          pop    cx
  190.          ret
  191. ENDP
  192.  
  193. PROC     SetBit NEAR
  194. ; Set a bit, bit number in DX:AX, table pointed to by DS:SI, size of
  195. ; table in bytes in DI.  Stomps BX.  Value of original bit in flags, Z/NZ.
  196.          push   cx
  197.          push   dx
  198.          push   ax
  199.          mov    cl,al         ; bl := bit mask
  200.          and    cl,07h
  201.          mov    bl,80h
  202.          shr    bl,cl
  203.          shr    dx,1          ; dx:ax := byte offset
  204.          rcr    ax,1
  205.          shr    dx,1
  206.          rcr    ax,1
  207.          shr    dx,1
  208.          rcr    ax,1
  209.          cmp    di,dx         ; dx := byte offset MOD table size
  210.          ja     @@quickdiv
  211.          mov    cx,di         ; (protect against overflow)
  212.          jcxz   @@notable
  213. @@protloop:
  214.          shl    cx,1
  215.          cmp    cx,dx
  216.          jbe    @@protloop
  217.          div    cx
  218.          mov    ax,dx
  219.          xor    dx,dx
  220. @@quickdiv:
  221.          div    di
  222.          mov    ax,si
  223.          add    si,dx         ; ds:si points to byte
  224.          mov    dl,[si]       ; save original
  225.          or     [si],bl       ; set bit
  226.          and    bl,dl         ; test original
  227.          mov    si,ax
  228. @@notable:
  229.          pop    ax
  230.          pop    dx
  231.          pop    cx
  232.          ret
  233. ENDP
  234.  
  235. PUBLIC   CountBits
  236. PROC     CountBits FAR inbuf:DWORD,inlen:WORD
  237. ; Count the ON bits in the input buffer, return result in DX:AX.
  238. ; Declare: Function CountBits(Var InBuf; InLen : Word) : LongInt;
  239. ; (Yeah, this really could be done more quickly with a translate table.)
  240.          push   ds
  241.          xor    bx,bx
  242.          mov    dx,bx
  243.          mov    cx,[inlen]
  244.          jcxz   @@nobuffer
  245.          lds    si,[inbuf]
  246.          cld
  247. @@byteloop:
  248.          lodsb
  249.          push   cx
  250.          mov    cx,8
  251. @@bitloop:
  252.          shl    al,1
  253.          adc    bx,00h
  254.          adc    dx,00h
  255.          loop   @@bitloop
  256.          pop    cx
  257.          loop   @@byteloop
  258. @@nobuffer:
  259.          mov    ax,bx
  260.          pop    ds
  261.          ret
  262. ENDP
  263.  
  264. PUBLIC   SetBloomFilter
  265. PROC     SetBloomFilter FAR inbuf:DWORD,inlen:WORD,bittable:DWORD,bittablelen:WORD,bitcount:WORD
  266. ; Hash the input buffer and set bitcount random bits in bittable which is
  267. ; bittablelen bytes long.  The PASCAL declaration is:
  268. ;
  269. ; Function SetBloomFilter(Var InBuf; InLen : Word; Var BitTable;
  270. ;                         BitTableLen, BitCount : Word) : Boolean;
  271. ;
  272. ; Stomps registers: AX,BX,CX,DX,ES,SI
  273.          push   ds
  274.          mov    ax,0FFFFh     ; initialize crc to -1
  275.          mov    dx,ax
  276.          mov    cx,[inlen]    ; cx := inlen
  277.          jcxz   @@crcdone
  278.          lds    si,[inbuf]    ; ds:si := ^inbuf
  279.          call   CRCBlock
  280. @@crcdone:
  281.          mov    bl,01h
  282.          push   bx
  283.          mov    cx,[bitcount]
  284.          jcxz   @@bitsdone
  285.          lds    si,[bittable]
  286.          mov    di,[bittablelen]
  287.          jmp    SHORT @@inbitloop
  288. @@bitloop:
  289.          call   NextNullCRC
  290. @@inbitloop:
  291.          call   SetBit
  292.          jnz    @@WasSet
  293.          pop    bx
  294.          xor    bl,bl
  295.          push   bx
  296. @@WasSet:
  297.          loop   @@bitloop
  298. @@bitsdone:
  299.          pop    ax
  300.          pop    ds
  301.          ret
  302. ENDP
  303.  
  304. PUBLIC   TestBloomFilter
  305. PROC     TestBloomFilter FAR inbuf:DWORD,inlen:WORD,bittable:DWORD,bittablelen:WORD,bitcount:WORD
  306. ; Hash the input buffer and test bitcount random bits in bittable which is
  307. ; bittablelen bytes long.  Stops at first zero bit.  The PASCAL declaration is:
  308. ;
  309. ; Function TestBloomFilter(Var InBuf; InLen : Word; Var BitTable;
  310. ;                          BitTableLen, BitCount : Word) : Boolean;
  311. ;
  312. ; Stomps registers: AX,BX,CX,DX,ES,SI
  313.          push   ds
  314.          mov    ax,0FFFFh     ; initialize crc to -1
  315.          mov    dx,ax
  316.          mov    cx,[inlen]    ; cx := inlen
  317.          jcxz   @@crcdone
  318.          lds    si,[inbuf]    ; ds:si := ^inbuf
  319.          call   CRCBlock
  320. @@crcdone:
  321.          mov    cx,[bitcount]
  322.          jcxz   @@nobits
  323.          lds    si,[bittable]
  324.          mov    di,[bittablelen]
  325.          jmp    SHORT @@inbitloop
  326. @@bitloop:
  327.          call   NextNullCRC
  328. @@inbitloop:
  329.          call   TestBit
  330.          jz     @@notin
  331.          loop   @@bitloop
  332. @@nobits:
  333.          mov    al,01h
  334.          jmp    SHORT @@bitsdone
  335. @@notin:
  336.          xor    al,al
  337. @@bitsdone:
  338.          pop    ds
  339.          ret
  340. ENDP
  341.  
  342. ENDS
  343. END
  344.